package 分类算法总的很好.剑指offer;
// https://leetcode-cn.com/problems/lian-xu-zi-shu-zu-de-zui-da-he-lcof/
public class 剑指Offer42连续子数组的最大和1003 {
    class Solution {
        //力扣
        // https://leetcode-cn.com/problems/lian-xu-zi-shu-zu-de-zui-da-he-lcof/
        public int maxSubArray(int[] nums) {
            int pre = 0, maxAns = nums[0];
            for (int x : nums) {
                pre = Math.max(pre + x, x);
                maxAns = Math.max(maxAns, pre);
            }
            return maxAns;
        }
        //牛客 动态规划
        //https://www.nowcoder.com/practice/459bd355da1549fa8a49e350bf3df484?tpId=117&&tqId=37797&rp=1&ru=/activity/oj&qru=/ta/job-code-high/question-ranking
        public int FindGreatestSumOfSubArray(int[] array) {
            int max = array[0];
            for (int i = 1; i < array.length; i++) {
                array[i] += array[i - 1] > 0 ? array[i - 1] : 0;
                max = Math.max(max, array[i]);
            }
            return max;
        }
    }
}
